package leetcode.hot100;

import java.util.LinkedList;
import java.util.Queue;

public class number994 {
    static int min=-1;
    public static void main(String[] args) {
        int [][]grid=new int[][]{{2,2},{1,1},{0,0},{2,0}};
        System.out.println(orangesRotting(grid));
    }
    public static int orangesRotting(int[][] grid) {
        Queue<int[]>queue=new LinkedList<>();
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==2){
                    queue.offer(new int[]{i,j});
                }
            }
        }
        bfs(grid,queue);
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    return -1;
                }
            }
        }
        return min==-1?0:min;
    }
    public static void bfs(int [][]grid,Queue<int[]> queue){
        if(queue.isEmpty()){
            return;
        }
        Queue<int []>nextQueue=new LinkedList<>();
        while(!queue.isEmpty()){
            int []xy= queue.poll();
            int i=xy[0];
            int j=xy[1];
            //往上
            if(i-1>=0&&grid[i-1][j]==1){
                grid[i-1][j]=2;
                nextQueue.offer(new int[]{i-1,j});
            }
            //往下
            if(i+1<grid.length&&grid[i+1][j]==1){
                grid[i+1][j]=2;
                nextQueue.offer(new int[]{i+1,j});
            }
            //往左
            if(j-1>=0&&grid[i][j-1]==1){
                grid[i][j-1]=2;
                nextQueue.offer(new int[]{i,j-1});
            }
            //往右
            if(j+1<grid[0].length&&grid[i][j+1]==1){
                grid[i][j+1]=2;
                nextQueue.offer(new int[]{i,j+1});
            }
        }
        bfs(grid,nextQueue);
        min++;
    }
}
